﻿using System;
using System.Collections.Generic;
using System.Text;

/*
	To do:
	extra chars.
	tidy up
*/

namespace Wildmatch
{
	class WildMatchWord
	{
		public String Word;
		public int Pos;
		public bool Finished { get { return (this.Pos < 0); } }
		
		public WildMatchWord(String theWord)
		{
			this.Word = theWord;
			this.Pos = 0;
		}

		public WildMatchWord(WildMatchWord src)
		{
			this.Word = src.Word;
			this.Pos = src.Pos;
		}

		public bool MatchChar(char c)
		{
			if (this.Pos < 0) return false;
			return (this.Word[this.Pos] == c);
		}

		public void Next()
		{
			if (this.Pos >= 0)
			{
				++this.Pos;
				if (this.Pos >= this.Word.Length)
					this.Pos = -1;
			}
		}
		
		public void Finish()
		{
			if (this.Pos > 0) this.Pos = -1;
		}
	}
	
	class MatchState
	{
		public MatchState(String target)
		{
			this.Process(target);
		}

		public MatchState(MatchState src)
		{
			this.words = new List<WildMatchWord>();
			foreach (WildMatchWord wmw in src.Words)
			{
				this.words.Add(new WildMatchWord(wmw));
			}
		}

		public void FinishWord(String word)
		{
			foreach (WildMatchWord wmw in this.words)
			{
				if (wmw.Word == word && !wmw.Finished)
				{
					wmw.Finish();
					break;
				}
			}
		}

		public List<WildMatchWord> Words { get { return this.words; } }

		void Process(String target)
		{
			// remove/replace noise
			String [] words = target.Split(' ');
			this.words = new List<WildMatchWord>();
			foreach (String word in words)
			{
				if (word.Length > 0)
				{
					this.words.Add(new WildMatchWord(word.ToUpper()));
				}
			}
		}

		List<WildMatchWord> words;
	}
	
	class WildMatch
	{
		public static bool Match(String target, String part)
		{
			if (target.Length == 0)
				return (part.Length == 0); // T matches empty to empty F otherwise
			if (part.Length == 0)
				return true;               // anything matches an empty search string 
			
			String seek = part.Replace(","," ")
							  .Replace("-", " ")
							  .Replace("_", " ")
							  .Replace(".", " ")
							  .Replace(",", " ")
							  .Replace("/", " ")
							  .Replace(" ", "")
							  .ToUpper();
			MatchState state = new MatchState(target.Replace(",", " ")
											  .Replace("-", " ")
											  .Replace("_", " ")
											  .Replace(".", " ")
											  .Replace(",", " ")
											  .Replace("/", " ")
												);

			// seeds a search starting from word 0
			return new WildMatch().MatchFrom(0, seek, 0, state);
		}

		// function to search from a given position in the seek string with 
		// a given match state for the words.
		public bool MatchFrom(int wordIndex, String seek, int fromPos, MatchState state)
		{
			if (fromPos >= seek.Length) return true; // recursive exit point
			// get the target char
			char seekChar = seek[fromPos];
			// start at -1 to give priority to the word index parameter
			for (int idx = -1; idx < state.Words.Count; ++idx)
			{
				if (idx >= 0) wordIndex = idx; // after -1 normal sequence.
				WildMatchWord wmw  = state.Words[wordIndex];
				// if a word has been consumed or part-consumed then it can't be re-used
				if (!wmw.Finished) // can't use this one if it is consumed
				{
					// match current char in current target word with then seek string char
					if (wmw.MatchChar(seekChar))
					{
						// consume the char in the target
						wmw.Next();
						// try to match the next seek string char with the next char in this word
						if (this.MatchFrom(wordIndex, seek, fromPos + 1, new MatchState(state)))
							// return success back up the recursive stack
							return true;
					}
				}
				// as the recusive function failed for this word at this point
				// it can play no further part in the matching process. So flag it.
				// ... unless this is the front of the word in which case in may be used
				// in another position eg AN APPLE matching APAN
				if (fromPos > 0) 
					wmw.Finish();
				else
					// wind it back to the start
					wmw.Pos = 0;
			}
			return false;
		}
	}
}
